package com.gitee.feizns.explore.data_structure.tree.cus.ttt;

import com.gitee.feizns.explore.data_structure.tree.cus.PutRet;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.OptionalInt;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;
import java.util.function.BiConsumer;
import java.util.function.Consumer;
import java.util.stream.Collectors;

/**
 * @author feizns
 * @since 2019/11/29
 */
public class TttImpl2<K extends Comparable<K>, V> implements Ttt<K, V> {

    private static Random random = new Random();

    public static void main(String[] args) {
        TttImpl2<Integer, String> ttt = new TttImpl2<>();
        for (int i = 0; i < 10000; i++) {
            Integer nextInt = random.nextInt(10000);
            ttt.put(nextInt, nextInt.toString());
        }
        System.out.println(ttt.get(27));
    }

    @Override
    public void recursiveBeforeEach(BiConsumer<K, V> consumer) {
        recursiveBeforeEach(root, consumer);
    }

    @Override
    public void recursiveMiddleEach(BiConsumer<K, V> consumer) {

    }

    private void recursiveBeforeEach(TTNode<K, V> node, BiConsumer<K, V> consumer) {
        if ( node != null ) {
            node.forEach(consumer);
            node.forEachNodes(n -> recursiveBeforeEach(n, consumer));
        }
    }

    @Override
    public void recursiveAfterEach(BiConsumer<K, V> consumer) {
        recursiveAfterEach(root, consumer);
    }

    private void recursiveAfterEach(TTNode<K, V> node, BiConsumer<K, V> consumer) {
        if ( node != null ) {
            node.forEachNodes(n -> recursiveBeforeEach(n, consumer));
            node.forEach(consumer);
        }
    }

    @Override
    public void recursiveSequenceTraversal(BiConsumer<K, V> consumer) {
        Queue<TTNode<K, V>> queue = new LinkedList<>();
        queue.add(root);
        recursiveSequenceTraversal(queue, consumer);
    }

    public void recursiveSequenceTraversal(Queue<TTNode<K, V>> queue, BiConsumer<K, V> consumer) {
        Queue<TTNode<K, V>> newQueue = new LinkedList<>();
        while ( !queue.isEmpty() ) {
            TTNode<K, V> node = queue.remove();
            node.forEach(consumer);
            node.forEachNodes(n -> newQueue.add(n));
        }
        if ( !newQueue.isEmpty() )
            recursiveSequenceTraversal(newQueue, consumer);
    }

    @Override
    public void beforeEach(BiConsumer<K, V> consumer) {
        Stack<TTNode<K, V>> stack = new Stack<>();
        while ( !stack.isEmpty() ) {
            TTNode<K, V> node = stack.pop();
            node.forEach(consumer);
            node.reverseEachNodes(stack::push);
        }
    }

    @Override
    public void middleEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void afterEach(BiConsumer<K, V> consumer) {
        Stack<TTNode<K, V>> stack = new Stack<>();
        Stack<TTNode<K, V>> tmpStack = new Stack<>();
        while ( !stack.isEmpty() ) {
            TTNode<K, V> node = stack.pop();
            tmpStack.push(node);
            node.forEachNodes(n -> tmpStack.add(n));
        }

        while ( !tmpStack.isEmpty() ) {
            TTNode<K, V> node = tmpStack.pop();
            node.forEach(consumer);
        }
    }

    @Override
    public void sequenceTraversal(BiConsumer<K, V> consumer) {
        Queue<TTNode<K, V>> queue = new LinkedList<>();
        queue.add(root);
        while ( !queue.isEmpty() ) {
            TTNode<K, V> node = queue.remove();
            node.forEach(consumer);
            node.forEachNodes(queue::add);
        }
    }

    TTNode<K, V> root;

    int size;

    @Override
    public int size() {
        return size;
    }

    @Override
    public V get(Object key) {
        return get(root, (K) key);
    }

    private V get(TTNode<K, V> root, K k) {
        if ( root != null ) {
            List<Entry> entries = root.entries();
            for (int i = 0; i < entries.size(); i++) {
                Entry<K, V> entry = entries.get(i);
                int comp = k.compareTo(entry.getKey());
                if ( comp == 0 )
                    return entry.getValue();
                else if ( comp < 0 )
                    return get(root.get(i), k);
                else if ( comp > 0 && i == entries.size() - 1 )
                    return get(root.get(entries.size()), k);
            }
        }
        return null;
    }

    @Override
    public V put(K key, V value) {
        PutRet<TTNode<K, V>, V> ret = put(root, key, value);
        root = ret.node();
        return ret.v();
    }

    private PutRet<TTNode<K, V>, V> put(TTNode<K, V> root, K k, V v) {
        if ( root == null ) {
            size++;
            return new PutRet<>(new TTNode<>(new EntryImpl<>(k, v)), null);
        }

        int nextIndex = -1;
        List<Entry> entries = root.entries();
        for (int i = 0; i < entries.size(); i++) {
            Entry<K, V> entry = entries.get(i);
            int comp = k.compareTo(entry.getKey());
            if ( comp == 0 )
                return new PutRet<>(root, entry.setValue(v));
            else if ( comp < 0 ) {
                nextIndex = i;
                break;
            } else if ( comp > 0 && i == entries.size() - 1 )
                nextIndex = entries.size();
        }

        if ( nextIndex != -1 ) {
            PutRet<TTNode<K, V>, V> ret = put(root.get(nextIndex), k, v);
            TTNode<K, V> node = ret.node();
            if ( node.height == root.height ) {
                root.set(nextIndex, null);
                TTNode<K, V> newRoot = merge(root, node);
                if ( isFull(newRoot) )
                    newRoot = split(newRoot);
                return new PutRet<>(newRoot, ret.v());
            } else {
                root.set(nextIndex, node);
            }
            return new PutRet<>(root, ret.v());
        }

        //叶子节点融合与分裂
        TTNode<K, V> node = merge(root, k, v);
        if ( isFull(node) )
            return new PutRet<>(split(node), null);

        return new PutRet<>(node, null);
    }

    private TTNode<K, V> merge(TTNode<K, V> node, K k, V v) {
        List<Entry> entries = node.entries();
        int newIndex = entries.size();
        for (int j = 0; j < entries.size(); j++) {
            Entry<K, V> entry = entries.get(j);
            int comp = k.compareTo(entry.getKey());
            if ( comp < 0 ) {
                newIndex = j;
                break;
            }
        }
        List<Entry> newEntries = new ArrayList<>(node.entriesDefaultNull());
        newEntries.add(newIndex, new EntryImpl<>(k, v));
        List<TTNode> newTTNodes = new ArrayList<>(node.childNodesDefaultNull());
        newTTNodes.add(newIndex, null);
        return new TTNode(newEntries, newTTNodes);
    }

    private TTNode<K, V> merge(TTNode<K, V> root, TTNode<K, V> node) {
        List<Entry> entries = root.entries();
        int newIndex = entries.size();
        for (int j = 0; j < entries.size(); j++) {
            Entry<K, V> entry = entries.get(j);
            int comp = node.left.getKey().compareTo(entry.getKey());
            if ( comp < 0 ) {
                newIndex = j;
                break;
            }
        }
        List<Entry> newEntries = new ArrayList<>(root.entriesDefaultNull());
        newEntries.add(newIndex, node.left);
        List<TTNode> newTTNodes = new ArrayList<>(root.childNodesDefaultNull());
        newTTNodes.addAll(newIndex, node.childNodes());
        return new TTNode(newEntries, newTTNodes);
    }

    private TTNode<K, V> split(TTNode<K, V> node) {
        TTNode<K, V> left = new TTNode<>(node.left, node.lessLeft, node.lessMid);
        TTNode<K, V> right = new TTNode<>(node.right, node.lessRight, node.moreRight);
        TTNode<K, V> root = new TTNode<>(node.mid, left, right);
        return root;
    }

    private boolean isFull(TTNode<K, V> node) {
        return Arrays.asList(node.left, node.mid, node.right).stream().allMatch(Objects::nonNull);
    }

    @Override
    public V remove(Object key) {
//        PutRet<TTNode, V> ret = remove(root, (K) key);
//        root = ret.node();
//        return ret.v();
        return null;
    }

//    private PutRet<TTNode, V> remove(TTNode root, K k) {
//        if ( root != null ) {
//            List<Entry> entries = root.entries();
//            int next = -1;
//            for (int i = 0; i < entries.size(); i++) {
//                Entry<K, V> entry = entries.get(i);
//                int comp = k.compareTo(entry.getKey());
//                if ( comp == 0 ) {
//                    if ( root.uniqueNode() ) {
//                        TTNode left = root.get(i);
//                        if ( left == null )
//                            return new PutRet<>(null, entry.getValue());
//
//                        TTNode min = min(root.lessMid);
//                        PutRet<TTNode, V> ret = remove(root.lessMid, (K) min.left.getKey());
//                        min.lessLeft = root.lessLeft;
//                        min.lessMid = ret.node();
//                        return new PutRet<>(min, entry.getValue());
//                    } else {
//
//                    }
//                } else if ( comp < 0 )
//                    next = i;
//                else if ( comp > 0 && i == entries.size() - 1 )
//                    next = entries.size();
//            }
//        }
//        return null;
//    }

    private TTNode min(TTNode root) {
        TTNode min = root;
        while ( min.lessLeft != null )
            min = min.lessLeft;
        return min;
    }

    @Override
    public void clear() {
        this.root = null;
        this.size = 0;
    }

    @Override
    public Set<K> keySet() {
        return entrySet().stream().map(Entry::getKey).collect(Collectors.toSet());
    }

    @Override
    public Collection<V> values() {
        return entrySet().stream().map(Entry::getValue).collect(Collectors.toList());
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        Set<Entry<K, V>> entries = new TreeSet<>();
        sequenceTraversal((k, v) -> entries.add(new EntryImpl<>(k, v)));
        return entries;
    }

    static class TTNode<K extends Comparable<K>, V> {

        int height;

        Entry<K, V> left;
        Entry<K, V> mid;
        Entry<K, V> right;

        TTNode<K, V> lessLeft;
        TTNode<K, V> lessMid;
        TTNode<K, V> lessRight;
        TTNode<K, V> moreRight;

        public void add(Entry<K, V> entry) {
            if ( left == null )
                left = entry;
            else if ( mid == null )
                mid = entry;
            else if ( right == null )
                right = entry;
        }

        public TTNode<K, V> get(int i) {
            if ( i == 0 )
                return lessLeft;
            else if ( i == 1 )
                return lessMid;
            else if ( i == 2 )
                return lessRight;
            else if ( i == 3 )
                return moreRight;
            return null;
        }

        public void set(int i, TTNode<K, V> node) {
            if ( i == 0 )
                lessLeft = node;
            else if ( i == 1 )
                lessMid = node;
            else if ( i == 2 )
                lessRight = node;
            else if ( i == 3 )
                moreRight = node;
        }

        public boolean uniqueNode() {
            return left != null && mid == null && right == null;
        }

        public boolean isEmpty() {
            return Arrays.stream(new TTNode[]{ lessLeft, lessMid, lessRight, moreRight }).allMatch(Objects::isNull);
        }

        public List<Entry> entries() {
            return Arrays.stream(new Entry[] { left, mid, right }).filter(Objects::nonNull).collect(Collectors.toList());
        }

        public List<Entry> entriesDefaultNull() {
            return Arrays.stream(new Entry[] { left, mid, right }).collect(Collectors.toList());
        }

        public List<TTNode> childNodes() {
            return Arrays.stream(new TTNode[] {lessLeft, lessMid, lessRight, moreRight}).filter(Objects::nonNull).collect(Collectors.toList());
        }

        public List<TTNode> childNodesDefaultNull() {
            return Arrays.stream(new TTNode[] {lessLeft, lessMid, lessRight, moreRight}).collect(Collectors.toList());
        }

        public TTNode(List<Entry<K, V>> entries, List<TTNode<K, V>> nodes) {
            for (int i = 0; i < 3 && i < entries.size(); i++)
                add(entries.get(i));
            for (int i = 0; i < 4; i++)
                set(i, nodes.get(i));
            this.height = h();
        }

        public TTNode(Entry<K, V> entry) {
            left = entry;
            height = 1;
        }

        public TTNode(Entry<K, V> entry, TTNode<K, V> lessLeft, TTNode<K, V> lessMid) {
            this(entry);
            this.lessLeft = lessLeft;
            this.lessMid = lessMid;
            this.height = h();
        }

        private int h() {
            List<TTNode> nodes = childNodes();
            OptionalInt max = nodes.stream().mapToInt(n -> h(n)).max();
            int h = max.orElse(0);
            return h + 1;
        }

        private int h(TTNode<K, V> node) {
            return node == null ? 0 : node.height;
        }

        public void forEach(BiConsumer<K, V> consumer) {
            consumeEntry(left, consumer);
            consumeEntry(mid, consumer);
            consumeEntry(right, consumer);
        }

        public void forEachNodes(Consumer<TTNode> consumer) {
            childNodes().stream().forEach(consumer);
        }

        public void reverseEachNodes(Consumer<TTNode<K, V>> consumer) {
            List<TTNode> nodes = childNodes();
            for (int i = nodes.size() - 1; i >= 0; i++)
                consumer.accept(nodes.get(i));
        }

        private void consumeEntry(Entry<K, V> entry, BiConsumer<K, V> consumer) {
            if ( entry != null )
                consumer.accept(entry.getKey(), entry.getValue());
        }

        private void consumeNode(TTNode<K, V> node, Consumer<TTNode<K, V>> consumer) {
            if ( node != null )
                consumer.accept(node);
        }

    }

    static class EntryImpl<K, V> implements Entry<K, V> {

        K k;

        V v;

        public EntryImpl(K k, V v) {
            this.k = k;
            this.v = v;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }

        @Override
        public V setValue(V value) {
            V old = v;
            v = value;
            return old;
        }

    }

}
